package com.gxc.tree;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * 给定长度为 n nn 的无序的数字数组，每个数字代表二叉树的叶子节点的权值，数字数组的值均大于等于 1 11 。请完成一个函数，根据输入的数字数组，生成哈夫曼树，并将哈夫曼树按照中序遍历输出。
 *
 * 为了保证输出的二叉树中序遍历结果统一，增加以下限制:又树节点中，左节点权值小于等于右节点权值，根节点权值为左右节点权值之和。当左右节点权值相同时，左子树高度高度小于等于右子树。
 *
 * 注意: 所有用例保证有效，并能生成哈夫曼树提醒:哈夫曼树又称最优二叉树，是一种带权路径长度最短的一叉树。
 *
 * 所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为 0 00 层，叶结点到根结点的路径长度为叶结点的层数)
 *
 * 输入描述
 * 例如：由叶子节点 5 15 40 30 10 生成的最优二叉树如下图所示，该树的最短带权路径长度为 40 * 1 + 30 * 2 +5 * 4 + 10 * 4 = 205 。
 *
 * 输出描述
 * 输出一个哈夫曼的中序遍历数组，数值间以空格分隔
 */
public class HuffmanTree {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }
        scanner.close();

        Node root = buildHuffmanTree(array);

        StringBuilder builder = new StringBuilder();
        inorderTraversal(root, builder);
        builder.deleteCharAt(builder.length() - 1);
        System.out.println(builder);
    }

    /**
     * 递归中序打印
     * @param root
     * @param builder
     */
    private static void inorderTraversal(Node root, StringBuilder builder) {
        if (root != null) {
            inorderTraversal(root.left, builder);
            builder.append(root.value).append(" ");
            inorderTraversal(root.right, builder);
        }
    }

    /**
     * 小跟堆构建哈夫曼树
     * @param array
     * @return
     */
    private static Node buildHuffmanTree(int[] array) {
        PriorityQueue<Node> pq = new PriorityQueue<>(new Compare());
        for (int i = 0; i < array.length; i++) {
            pq.offer(new Node(array[i]));
        }

        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();

            Node parent = new Node(left.value + right.value);
            if (left.value > right.value || (left.value == right.value && left.height>right.height)) {
                Node temp = left;
                left = right;
                right = temp;
            }
            parent.left = left;
            parent.right = right;
            parent.height = Math.max(left.height, right.height) + 1;
            pq.offer(parent);
        }
        return pq.peek();
    }
}

class Node {

    public int height;
    public Node left;
    public Node right;
    public int value;

    public Node(int value) {
        this.value = value;
        this.height = 0;
    }
}

class Compare implements Comparator<Node> {

    @Override
    public int compare(Node o1, Node o2) {
        if (o1.value > o2.value) return 1;
        if (o2.value > o1.value) return -1;
        if (o1.height > o2.height) return 1;
        if (o2.height > o1.height) return -1;
        return 0;
    }
}
